class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>>  dp(n, vector<bool>(n));
        int len = 1, begin = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j] && len < j - i + 1)
                    len = j - i + 1, begin = i;
            }
        }
        return s.substr(begin, len);
    }
};
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        unordered_map<long long, vector<int>> hash;
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);
        int ret = 0;
        for (int j = 2; j < n; j++) {
            for (int i = 1; i < j; i++) {
                long long a = (long long)2 * nums[i] - nums[j];
                if (hash.count(a)) {
                    for (int k : hash[a]) {
                        if (k < i) dp[i][j] += dp[k][i] + 1;
                    }
                }
                ret += dp[i][j];
            }
        }
        return ret;
    }
};